package com.algorithm;


import java.util.Arrays;

/**
 * 跳跃游戏（动态规划）
 */
public class JumpGame {

    public static boolean canJump(int[] nums) {
//        int[] temp = new int[nums.length];
//        Arrays.fill(temp, 0);
//        temp[nums.length - 1] = 1;
//        boolean b = doJump(0, temp, nums);
//        return b;

//        int length = nums.length;
//        int[] temp = new int[length];
//        Arrays.fill(temp, 0);
//        temp[nums.length - 1] = 1;
//        for (int i = length - 2; i >= 0; i--) {
//            int min = Math.min(i + nums[i], length - 1);
//            for (int j = i+1; j <= min; j++) {
//                if(temp[j]==1){
//                    temp[i]=1;
//                    break;
//                }
//            }
//        }
//        if(temp[0]==1){
//            return true;
//        }
//        return false;

        //贪心算法后往前
//        int length = nums.length;
//        int maxPos=length-1;
//        for (int i = length - 2; i >= 0; i--) {
//            if (i+nums[i]>=maxPos){
//                maxPos=i;
//            }
//        }
//        if (maxPos==0){
//            return true;
//        }
//        return false;
        //贪心算法前往后
        int n = nums.length;
        int rightmost = 0;
        for (int i = 0; i < n; ++i) {
            //如果超过了最大坐标位置就返回false
            if(i>rightmost){
                return false;
            }
            if (i <= rightmost) {
                rightmost = Math.max(rightmost, i + nums[i]);
                if (rightmost >= n - 1) {
                    return true;
                }
            }
        }
        return false;

    }

    public static void main(String[] args) {
//        int[] nums = {2, 3, 1, 1, 4};
//        int[] nums = {3, 2, 1, 0, 4};
        int[] nums = {3, 2, 0,0,0,1, 0, 4};
        boolean b = canJump(nums);
        System.out.println(b);
    }

    public static boolean doJump(int index, int[] temp, int[] nums) {
        if (temp[index] == 1) {
            return true;
        } else if (temp[index] == -1) {
            return false;
        } else {
            int maxPos = Math.min(index + nums[index], nums.length - 1);
            for (int i = index + 1; i <= maxPos; i++) {
                boolean b = doJump(i, temp, nums);
                if (b) {
                    temp[index] = 1;
                    return true;
                }
            }
        }
        temp[index] = -1;
        return false;
    }


}
